package com.zdp.leetcodeMiddle;


import com.zdp.util.TreeNode;

/*
* 题目描述：
* 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，
* 其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
* 若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
提示：
树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是 完全二叉树
进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-complete-tree-nodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 完全二叉树的节点个数_222 {

    /*
    * 解法一 ： 直接记录 即可
    * */
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        // 1 代表自身
        return countNodes(root.left) + countNodes(root.right) +1;
    }


    /*
    * 解法2 ： 根据 完全二叉树的特性 ： 完全二叉树 从左到右填充，所以 左子树的高度一定是 大于或者等于 右子树的
    *  计算 左右子树的高度
    * 若 left == right  说明 节点已经填充到右子树了 ---> 左子树为满二叉树  对右子树进行递归统计
    *  若 left> right  说明节点还未填充到右子树 ---> 右子树为满二叉树  对左子树进行递归统计
    * */
    public int countNodes1(TreeNode root) {

        if(root == null){
            return 0;
        }
        int left = countLevel(root.left);
        int right = countLevel(root.right);
        if(left== right){
            return countNodes1(root.right) + (1<<left);
        }else{
            return countNodes1(root.left) + (1<<right);
        }
    }

    public int countLevel(TreeNode t){
        int level = 0;
        while(t!=null){
            t = t.left;
            level++;
        }
        return level;
    }
}
